home *** CD-ROM | disk | FTP | other *** search
/ Chip 2007 January, February, March & April / Chip-Cover-CD-2007-02.iso / Pakiet bezpieczenstwa / mini Pentoo LiveCD 2006.1 / mpentoo-2006.1.iso / livecd.squashfs / usr / lib / python2.4 / site-packages / Crypto / Protocol / Chaffing.py < prev   
Text File  |  2006-06-22  |  9KB  |  230 lines
  1. """This file implements the chaffing algorithm.
  2.  
  3. Winnowing and chaffing is a technique for enhancing privacy without requiring
  4. strong encryption.  In short, the technique takes a set of authenticated
  5. message blocks (the wheat) and adds a number of chaff blocks which have
  6. randomly chosen data and MAC fields.  This means that to an adversary, the
  7. chaff blocks look as valid as the wheat blocks, and so the authentication
  8. would have to be performed on every block.  By tailoring the number of chaff
  9. blocks added to the message, the sender can make breaking the message
  10. computationally infeasible.  There are many other interesting properties of
  11. the winnow/chaff technique.
  12.  
  13. For example, say Alice is sending a message to Bob.  She packetizes the
  14. message and performs an all-or-nothing transformation on the packets.  Then
  15. she authenticates each packet with a message authentication code (MAC).  The
  16. MAC is a hash of the data packet, and there is a secret key which she must
  17. share with Bob (key distribution is an exercise left to the reader).  She then
  18. adds a serial number to each packet, and sends the packets to Bob.
  19.  
  20. Bob receives the packets, and using the shared secret authentication key,
  21. authenticates the MACs for each packet.  Those packets that have bad MACs are
  22. simply discarded.  The remainder are sorted by serial number, and passed
  23. through the reverse all-or-nothing transform.  The transform means that an
  24. eavesdropper (say Eve) must acquire all the packets before any of the data can
  25. be read.  If even one packet is missing, the data is useless.
  26.  
  27. There's one twist: by adding chaff packets, Alice and Bob can make Eve's job
  28. much harder, since Eve now has to break the shared secret key, or try every
  29. combination of wheat and chaff packet to read any of the message.  The cool
  30. thing is that Bob doesn't need to add any additional code; the chaff packets
  31. are already filtered out because their MACs don't match (in all likelihood --
  32. since the data and MACs for the chaff packets are randomly chosen it is
  33. possible, but very unlikely that a chaff MAC will match the chaff data).  And
  34. Alice need not even be the party adding the chaff!  She could be completely
  35. unaware that a third party, say Charles, is adding chaff packets to her
  36. messages as they are transmitted.
  37.  
  38. For more information on winnowing and chaffing see this paper:
  39.  
  40. Ronald L. Rivest, "Chaffing and Winnowing: Confidentiality without Encryption"
  41. http://theory.lcs.mit.edu/~rivest/chaffing.txt
  42.  
  43. """
  44.  
  45. __revision__ = "$Id: Chaffing.py,v 1.7 2003/02/28 15:23:21 akuchling Exp $"
  46.  
  47. from Crypto.Util.number import bytes_to_long
  48.  
  49. class Chaff:
  50.     """Class implementing the chaff adding algorithm.
  51.  
  52.     Methods for subclasses:
  53.  
  54.             _randnum(size):
  55.                 Returns a randomly generated number with a byte-length equal
  56.                 to size.  Subclasses can use this to implement better random
  57.                 data and MAC generating algorithms.  The default algorithm is
  58.                 probably not very cryptographically secure.  It is most
  59.                 important that the chaff data does not contain any patterns
  60.                 that can be used to discern it from wheat data without running
  61.                 the MAC.
  62.  
  63.     """
  64.  
  65.     def __init__(self, factor=1.0, blocksper=1):
  66.         """Chaff(factor:float, blocksper:int)
  67.  
  68.         factor is the number of message blocks to add chaff to,
  69.         expressed as a percentage between 0.0 and 1.0.  blocksper is
  70.         the number of chaff blocks to include for each block being
  71.         chaffed.  Thus the defaults add one chaff block to every
  72.         message block.  By changing the defaults, you can adjust how
  73.         computationally difficult it could be for an adversary to
  74.         brute-force crack the message.  The difficulty is expressed
  75.         as:
  76.  
  77.             pow(blocksper, int(factor * number-of-blocks))
  78.  
  79.         For ease of implementation, when factor < 1.0, only the first
  80.         int(factor*number-of-blocks) message blocks are chaffed.
  81.         """
  82.  
  83.         if not (0.0<=factor<=1.0):
  84.             raise ValueError, "'factor' must be between 0.0 and 1.0"
  85.         if blocksper < 0:
  86.             raise ValueError, "'blocksper' must be zero or more"
  87.  
  88.         self.__factor = factor
  89.         self.__blocksper = blocksper
  90.  
  91.  
  92.     def chaff(self, blocks):
  93.         """chaff( [(serial-number:int, data:string, MAC:string)] )
  94.         : [(int, string, string)]
  95.  
  96.         Add chaff to message blocks.  blocks is a list of 3-tuples of the
  97.         form (serial-number, data, MAC).
  98.  
  99.         Chaff is created by choosing a random number of the same
  100.         byte-length as data, and another random number of the same
  101.         byte-length as MAC.  The message block's serial number is
  102.         placed on the chaff block and all the packet's chaff blocks
  103.         are randomly interspersed with the single wheat block.  This
  104.         method then returns a list of 3-tuples of the same form.
  105.         Chaffed blocks will contain multiple instances of 3-tuples
  106.         with the same serial number, but the only way to figure out
  107.         which blocks are wheat and which are chaff is to perform the
  108.         MAC hash and compare values.
  109.         """
  110.  
  111.         chaffedblocks = []
  112.  
  113.         # count is the number of blocks to add chaff to.  blocksper is the
  114.         # number of chaff blocks to add per message block that is being
  115.         # chaffed.
  116.         count = len(blocks) * self.__factor
  117.         blocksper = range(self.__blocksper)
  118.         for i, wheat in map(None, range(len(blocks)), blocks):
  119.             # it shouldn't matter which of the n blocks we add chaff to, so for
  120.             # ease of implementation, we'll just add them to the first count
  121.             # blocks
  122.             if i < count:
  123.                 serial, data, mac = wheat
  124.                 datasize = len(data)
  125.                 macsize = len(mac)
  126.                 addwheat = 1
  127.                 # add chaff to this block
  128.                 for j in blocksper:
  129.                     import sys
  130.                     chaffdata = self._randnum(datasize)
  131.                     chaffmac = self._randnum(macsize)
  132.                     chaff = (serial, chaffdata, chaffmac)
  133.                     # mix up the order, if the 5th bit is on then put the
  134.                     # wheat on the list
  135.                     if addwheat and bytes_to_long(self._randnum(16)) & 0x40:
  136.                         chaffedblocks.append(wheat)
  137.                         addwheat = 0
  138.                     chaffedblocks.append(chaff)
  139.                 if addwheat:
  140.                     chaffedblocks.append(wheat)
  141.             else:
  142.                 # just add the wheat
  143.                 chaffedblocks.append(wheat)
  144.         return chaffedblocks
  145.  
  146.     def _randnum(self, size):
  147.         # TBD: Not a very secure algorithm.
  148.         # TBD: size * 2 to work around possible bug in RandomPool
  149.         from Crypto.Util import randpool
  150.         import time
  151.         pool = randpool.RandomPool(size * 2)
  152.         while size > pool.entropy:
  153.             pass
  154.  
  155.         # we now have enough entropy in the pool to get size bytes of random
  156.         # data... well, probably
  157.         return pool.get_bytes(size)
  158.  
  159.  
  160.  
  161. if __name__ == '__main__':
  162.     text = """\
  163. We hold these truths to be self-evident, that all men are created equal, that
  164. they are endowed by their Creator with certain unalienable Rights, that among
  165. these are Life, Liberty, and the pursuit of Happiness. That to secure these
  166. rights, Governments are instituted among Men, deriving their just powers from
  167. the consent of the governed. That whenever any Form of Government becomes
  168. destructive of these ends, it is the Right of the People to alter or to
  169. abolish it, and to institute new Government, laying its foundation on such
  170. principles and organizing its powers in such form, as to them shall seem most
  171. likely to effect their Safety and Happiness.
  172. """
  173.     print 'Original text:\n=========='
  174.     print text
  175.     print '=========='
  176.  
  177.     # first transform the text into packets
  178.     blocks = [] ; size = 40
  179.     for i in range(0, len(text), size):
  180.         blocks.append( text[i:i+size] )
  181.  
  182.     # now get MACs for all the text blocks.  The key is obvious...
  183.     print 'Calculating MACs...'
  184.     from Crypto.Hash import HMAC, SHA
  185.     key = 'Jefferson'
  186.     macs = [HMAC.new(key, block, digestmod=SHA).digest()
  187.             for block in blocks]
  188.  
  189.     assert len(blocks) == len(macs)
  190.  
  191.     # put these into a form acceptable as input to the chaffing procedure
  192.     source = []
  193.     m = map(None, range(len(blocks)), blocks, macs)
  194.     print m
  195.     for i, data, mac in m:
  196.         source.append((i, data, mac))
  197.  
  198.     # now chaff these
  199.     print 'Adding chaff...'
  200.     c = Chaff(factor=0.5, blocksper=2)
  201.     chaffed = c.chaff(source)
  202.  
  203.     from base64 import encodestring
  204.  
  205.     # print the chaffed message blocks.  meanwhile, separate the wheat from
  206.     # the chaff
  207.  
  208.     wheat = []
  209.     print 'chaffed message blocks:'
  210.     for i, data, mac in chaffed:
  211.         # do the authentication
  212.         h = HMAC.new(key, data, digestmod=SHA)
  213.         pmac = h.digest()
  214.         if pmac == mac:
  215.             tag = '-->'
  216.             wheat.append(data)
  217.         else:
  218.             tag = '   '
  219.         # base64 adds a trailing newline
  220.         print tag, '%3d' % i, \
  221.               repr(data), encodestring(mac)[:-1]
  222.  
  223.     # now decode the message packets and check it against the original text
  224.     print 'Undigesting wheat...'
  225.     newtext = "".join(wheat)
  226.     if newtext == text:
  227.         print 'They match!'
  228.     else:
  229.         print 'They differ!'
  230.